Dat je niz od n celih brojeva. Pronaći najveći zbir nekih elemenata niza, tako da ako je a_i u zbiru ni a_i − 1 ni a_i + 1 nisu u zbiru. Potrebno je napisati efikasno rešenje čija je vremenska složenost O(n).

Ulaz

Sa standardnog ulaza se unosi broj n ∈ [2,50000], a zatim i n celih brojeva iz intervala [0,10000].

Izlaz

Na standardni izlaz ispisati jedan broj - maksimalni zbir odredjenih elemenata niza.

Primer 1

Ulaz

5
3 4 3 4 3

Izlaz

9

Primer 2

Ulaz

6
3 4 1 1 4 1

Izlaz

8